package com.lw.leetcode.tree.b;

import com.lw.leetcode.linked.ListNode;
import com.lw.leetcode.tree.TreeNode;

/**
 * @Author liw
 * @Date 2021/5/13 14:43
 * @Version 1.0
 */
public class SortedListToBST {

    public static void main(String[] args) {
        SortedListToBST a = new SortedListToBST();

        ListNode instance = ListNode.getInstance();

        TreeNode node = a.sortedListToBST(instance);
        System.out.println(node);
    }

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        } else if(head.next == null) {
            return new TreeNode(head.val);
        }
        ListNode a = head;
        ListNode b = head;
        ListNode item = head;
        while (b != null && b.next != null) {
            item = a;
            a = a.next;
            b = b.next.next;
        }
        item.next = null;
        TreeNode node = new TreeNode(a.val);
        node.left = sortedListToBST(head);
        node.right = sortedListToBST(a.next);
        return node;
    }

}
